package leetcode;

import java.awt.font.NumericShaper;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode120 {

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>(
                Arrays.asList(Arrays.asList(2),
                        Arrays.asList(3, 4),
                        Arrays.asList(6, 5, 7),
                        Arrays.asList(4, 1, 8, 3)));

        LeetCode120 leetCode120 = new LeetCode120();
        leetCode120.minimumTotal(triangle);
    }

    //递归超出时间限制
    int min = Integer.MAX_VALUE;

    int[][] cache;

    public int minimumTotal1(List<List<Integer>> triangle) {
        cache = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
        cache[0][0] = triangle.get(0).get(0);
        helper(0, 0, 0, triangle);
        return min;
    }

    //加入缓存  因为同一个格子的数据别重复计算两次
    private void helper(int row, int column, int lastResult, List<List<Integer>> triangle) {
        int num;
        if (cache[row][column] != 0)
            num = cache[row][column];
        else {
            num = lastResult + triangle.get(row).get(column);
            cache[row][column] = num;
        }
        if (row == triangle.size() - 1) {
            min = Math.min(min, num);
            return;
        } else {
            helper(row + 1, column, num, triangle);
            helper(row + 1, column + 1, num, triangle);
        }
    }

    // dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+row[i][j]
//------------------------------------------------------------------

    public int minimumTotal(List<List<Integer>> triangle) {
        // 特判
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }

        int row = triangle.size();
        int column = triangle.get(row - 1).size();

        int[][] dp = new int[row][column];
        dp[0][0] = triangle.get(0).get(0);
        int res = Integer.MAX_VALUE;

        for (int i = 1; i < row; i++) {
            //对每一行的元素进行推导
            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    // 最左端特殊处理
                    dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j);
                } else if (j == i) {
                    // 最右端特殊处理
                    dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
                }
            }
        }

        // dp最后一行记录了最小路径
        for (int i = 0; i < column; i++) {
            res = Math.min(res, dp[row - 1][i]);
        }
        return res;
    }
}
